/*
 * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   * Redistributions of source code must retain the above copyright notice,
 *     this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *   * Neither the name of Redis nor the names of its contributors may be used
 *     to endorse or promote products derived from this software without
 *     specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include "../lib/server.h"

/*-----------------------------------------------------------------------------
 * List API
 *----------------------------------------------------------------------------*/

/* The function pushes an element to the specified list object 'subject',
 * at head or tail position as specified by 'where'.
 *
 * There is no need for the caller to increment the refcount of 'value' as
 * the function takes care of it if needed. */
void listTypePush ( robj *subject, robj *value, int where )
{
    if ( subject->encoding == OBJ_ENCODING_QUICKLIST )
    {
        int pos = ( where == LIST_HEAD ) ? QUICKLIST_HEAD : QUICKLIST_TAIL;
        value = getDecodedObject (value);
        size_t len = sdslen (value->ptr);
        quicklistPush (subject->ptr, value->ptr, len, pos);
        decrRefCount (value);
    }
}

void *listPopSaver ( unsigned char *data, unsigned int sz )
{
    return createStringObject (( char* ) data, sz);
}

robj *listTypePop ( robj *subject, int where )
{
    long long vlong;
    robj *value = NULL;

    int ql_where = where == LIST_HEAD ? QUICKLIST_HEAD : QUICKLIST_TAIL;
    if ( subject->encoding == OBJ_ENCODING_QUICKLIST )
    {
        if ( quicklistPopCustom (subject->ptr, ql_where, ( unsigned char ** ) &value,
                                 NULL, &vlong, listPopSaver) )
        {
            if ( ! value )
                value = createStringObjectFromLongLong (vlong);
        }
    }
    return value;
}

unsigned long listTypeLength ( robj *subject )
{
    if ( subject->encoding == OBJ_ENCODING_QUICKLIST )
    {
        return quicklistCount (subject->ptr);
    }
    return 0;
}

/* Initialize an iterator at the specified index. */
listTypeIterator *listTypeInitIterator ( robj *subject, long index,
                                         unsigned char direction )
{
    listTypeIterator *li = zmalloc (sizeof (listTypeIterator ));
    li->subject = subject;
    li->encoding = subject->encoding;
    li->direction = direction;
    li->iter = NULL;
    /* LIST_HEAD means start at TAIL and move *towards* head.
     * LIST_TAIL means start at HEAD and move *towards tail. */
    int iter_direction =
        direction == LIST_HEAD ? AL_START_TAIL : AL_START_HEAD;
    if ( li->encoding == OBJ_ENCODING_QUICKLIST )
    {
        li->iter = quicklistGetIteratorAtIdx (li->subject->ptr,
                                              iter_direction, index);
    }
    return li;
}

/* Clean up the iterator. */
void listTypeReleaseIterator ( listTypeIterator *li )
{
    zfree (li->iter);
    zfree (li);
}

/* Stores pointer to current the entry in the provided entry structure
 * and advances the position of the iterator. Returns 1 when the current
 * entry is in fact an entry, 0 otherwise. */
int listTypeNext ( listTypeIterator *li, listTypeEntry *entry )
{
    /* Protect from converting when iterating */

    entry->li = li;
    if ( li->encoding == OBJ_ENCODING_QUICKLIST )
    {
        return quicklistNext (li->iter, &entry->entry);
    }
    return 0;
}

/* Return entry or NULL at the current position of the iterator. */
robj *listTypeGet ( listTypeEntry *entry )
{
    robj *value = NULL;
    if ( entry->li->encoding == OBJ_ENCODING_QUICKLIST )
    {
        if ( entry->entry.value )
        {
            value = createStringObject (( char * ) entry->entry.value,
                                        entry->entry.sz);
        }
        else
        {
            value = createStringObjectFromLongLong (entry->entry.longval);
        }
    }
    return value;
}

void listTypeInsert ( listTypeEntry *entry, robj *value, int where )
{
    if ( entry->li->encoding == OBJ_ENCODING_QUICKLIST )
    {
        value = getDecodedObject (value);
        sds str = value->ptr;
        size_t len = sdslen (str);
        if ( where == LIST_TAIL )
        {
            quicklistInsertAfter (( quicklist * ) entry->entry.quicklist,
                                  &entry->entry, str, len);
        }
        else if ( where == LIST_HEAD )
        {
            quicklistInsertBefore (( quicklist * ) entry->entry.quicklist,
                                   &entry->entry, str, len);
        }
        decrRefCount (value);
    }
}

/* Compare the given object with the entry at the current position. */
int listTypeEqual ( listTypeEntry *entry, robj *o )
{
    if ( entry->li->encoding == OBJ_ENCODING_QUICKLIST )
    {
        return quicklistCompare (entry->entry.zi, o->ptr, sdslen (o->ptr));
    }
    return 0;
}

/* Delete the element pointed to. */
void listTypeDelete ( listTypeIterator *iter, listTypeEntry *entry )
{
    if ( entry->li->encoding == OBJ_ENCODING_QUICKLIST )
    {
        quicklistDelEntry (iter->iter, &entry->entry);
    }
}

/* Create a quicklist from a single ziplist */
void listTypeConvert ( robj *subject, int enc )
{

    if ( enc == OBJ_ENCODING_QUICKLIST )
    {
        size_t zlen = server.list_max_ziplist_size;
        int depth = server.list_compress_depth;
        subject->ptr = quicklistCreateFromZiplist (zlen, depth, subject->ptr);
        subject->encoding = OBJ_ENCODING_QUICKLIST;
    }
}

/*-----------------------------------------------------------------------------
 * List Commands
 *----------------------------------------------------------------------------*/

int pushGenericCommand ( client *c, int where )
{
    int j, waiting = 0, pushed = 0;
    robj *lobj = lookupKeyWrite (c->db, c->argv[1]);

    if ( lobj && lobj->type != OBJ_LIST )
    {
        return C_ERR;
    }

    for ( j = 2; j < c->argc; j ++ )
    {
        c->argv[j] = tryObjectEncoding (c->argv[j]);
        if ( ! lobj )
        {
            lobj = createQuicklistObject ();
            quicklistSetOptions (lobj->ptr, server.list_max_ziplist_size,
                                 server.list_compress_depth);
            dbAdd (c->db, c->argv[1], lobj);
        }
        listTypePush (lobj, c->argv[j], where);
        pushed ++;
    }
    addReplyLongLong (c, waiting + ( lobj ? listTypeLength (lobj) : 0 ));
    return C_OK;
}

int lpushCommand ( client *c )
{
    return pushGenericCommand (c, LIST_HEAD);
}

int rpushCommand ( client *c )
{
    return pushGenericCommand (c, LIST_TAIL);
}

int pushxGenericCommand ( client *c, robj *refval, robj *val, int where )
{
    robj *subject;
    listTypeIterator *iter;
    listTypeEntry entry;
    int inserted = 0;

    if ( ( subject = lookupKeyWrite (c->db, c->argv[1]) ) ||
         checkType (c, subject, OBJ_LIST) ) return C_ERR;

    if ( refval != NULL )
    {
        /* Seek refval from head to tail */
        iter = listTypeInitIterator (subject, 0, LIST_TAIL);
        while ( listTypeNext (iter, &entry) )
        {
            if ( listTypeEqual (&entry, refval) )
            {
                listTypeInsert (&entry, val, where);
                inserted = 1;
                break;
            }
        }
        listTypeReleaseIterator (iter);

        if ( ! inserted )
        {
            return C_ERR;
        }
    }
    else
    {

        listTypePush (subject, val, where);
    }

    addReplyLongLong (c, listTypeLength (subject));
    return C_OK;
}

int lpushxCommand ( client *c )
{
    c->argv[2] = tryObjectEncoding (c->argv[2]);
    return pushxGenericCommand (c, NULL, c->argv[2], LIST_HEAD);
}

int rpushxCommand ( client *c )
{
    c->argv[2] = tryObjectEncoding (c->argv[2]);
    return pushxGenericCommand (c, NULL, c->argv[2], LIST_TAIL);
}

int linsertCommand ( client *c )
{
    c->argv[4] = tryObjectEncoding (c->argv[4]);
    if ( strcasecmp (c->argv[2]->ptr, "after") == 0 )
    {
        return pushxGenericCommand (c, c->argv[3], c->argv[4], LIST_TAIL);
    }
    else if ( strcasecmp (c->argv[2]->ptr, "before") == 0 )
    {
        return pushxGenericCommand (c, c->argv[3], c->argv[4], LIST_HEAD);
    }
    return C_ERR;
}

int llenCommand ( client *c )
{
    robj *o = lookupKeyRead (c->db, c->argv[1]);
    if ( o == NULL || checkType (c, o, OBJ_LIST) ) return C_ERR;
    addReplyLongLong (c, listTypeLength (o));
    return C_OK;
}

int lindexCommand ( client *c )
{
    robj *o = lookupKeyRead (c->db, c->argv[1]);
    if ( o == NULL || checkType (c, o, OBJ_LIST) ) return C_ERR;
    long index;
    robj *value = NULL;

    if ( ( getLongFromObject (c->argv[2], &index) != C_OK ) )
        return C_ERR;

    if ( o->encoding == OBJ_ENCODING_QUICKLIST )
    {
        quicklistEntry entry;
        if ( quicklistIndex (o->ptr, index, &entry) )
        {
            if ( entry.value )
            {
                value = createStringObject (( char* ) entry.value, entry.sz);
            }
            else
            {
                value = createStringObjectFromLongLong (entry.longval);
            }
            addReply (c, value);
            decrRefCount (value);
        }
        else
        {
            return C_ERR;
        }
    }
    return C_OK;
}

int lsetCommand ( client *c )
{
    robj *o = lookupKeyWrite (c->db, c->argv[1]);
    if ( o == NULL || checkType (c, o, OBJ_LIST) ) return C_ERR;
    long index;
    robj *value = c->argv[3];

    if ( ( getLongFromObject (c->argv[2], &index) != C_OK ) )
        return C_ERR;

    if ( o->encoding == OBJ_ENCODING_QUICKLIST )
    {
        quicklist *ql = o->ptr;
        int replaced = quicklistReplaceAtIndex (ql, index,
                                                value->ptr, sdslen (value->ptr));
        if ( ! replaced )
        {
            return C_ERR;
        }
    }
    else
    {
        return C_ERR;
    }
    return C_OK;
}

int popGenericCommand ( client *c, int where )
{
    robj *o = lookupKeyWrite (c->db, c->argv[1]);
    if ( o == NULL || checkType (c, o, OBJ_LIST) ) return C_ERR;

    robj *value = listTypePop (o, where);
    if ( value == NULL )
    {
        return C_ERR;
    }
    else
    {
        addReply (c, value);
        decrRefCount (value);
        if ( listTypeLength (o) == 0 )
        {
            dbDelete (c->db, c->argv[1]);
        }
    }
    return C_OK;
}

int lpopCommand ( client *c )
{
    return popGenericCommand (c, LIST_HEAD);
}

int rpopCommand ( client *c )
{
    return popGenericCommand (c, LIST_TAIL);
}

int lrangeCommand ( client *c )
{
    robj *o;
    long start, end, llen, rangelen;

    if ( ( getLongFromObject (c->argv[2], &start) != C_OK ) ||
         ( getLongFromObject (c->argv[3], &end) != C_OK ) ) return C_ERR;

    if ( ( o = lookupKeyRead (c->db, c->argv[1]) ) == NULL
         || checkType (c, o, OBJ_LIST) ) return C_ERR;
    llen = listTypeLength (o);

    /* convert negative indexes */
    if ( start < 0 ) start = llen + start;
    if ( end < 0 ) end = llen + end;
    if ( start < 0 ) start = 0;

    /* Invariant: start >= 0, so this test will be true when end < 0.
     * The range is empty when start > end or start >= length. */
    if ( start > end || start >= llen )
    {
        return C_ERR;
    }
    if ( end >= llen ) end = llen - 1;
    rangelen = ( end - start ) + 1;

    /* Return the result in form of a multi-bulk reply */
    if ( o->encoding == OBJ_ENCODING_QUICKLIST )
    {
        listTypeIterator *iter = listTypeInitIterator (o, start, LIST_TAIL);

        while ( rangelen -- )
        {
            listTypeEntry entry;
            listTypeNext (iter, &entry);
            quicklistEntry *qe = & entry.entry;
            if ( qe->value )
            {
                addReplyString (c, ( char * ) qe->value, qe->sz);
            }
            else
            {
                addReplyLongLong (c, qe->longval);
            }
        }
        listTypeReleaseIterator (iter);
    }
    else
    {
        return C_ERR;
    }
    return C_OK;
}

int ltrimCommand ( client *c )
{
    robj *o;
    long start, end, llen, ltrim, rtrim;

    if ( ( getLongFromObject (c->argv[2], &start) != C_OK ) ||
         ( getLongFromObject (c->argv[3], &end) != C_OK ) ) return C_ERR;

    if ( ( o = lookupKeyWrite (c->db, c->argv[1]) ) == NULL ||
         checkType (c, o, OBJ_LIST) ) return C_ERR;
    llen = listTypeLength (o);

    /* convert negative indexes */
    if ( start < 0 ) start = llen + start;
    if ( end < 0 ) end = llen + end;
    if ( start < 0 ) start = 0;

    /* Invariant: start >= 0, so this test will be true when end < 0.
     * The range is empty when start > end or start >= length. */
    if ( start > end || start >= llen )
    {
        /* Out of range start or start > end result in empty list */
        ltrim = llen;
        rtrim = 0;
    }
    else
    {
        if ( end >= llen ) end = llen - 1;
        ltrim = start;
        rtrim = llen - end - 1;
    }

    /* Remove list elements to perform the trim */
    if ( o->encoding == OBJ_ENCODING_QUICKLIST )
    {
        quicklistDelRange (o->ptr, 0, ltrim);
        quicklistDelRange (o->ptr, - rtrim, rtrim);
    }
    else
    {
        return C_ERR;
    }

    if ( listTypeLength (o) == 0 )
    {
        dbDelete (c->db, c->argv[1]);
    }
    return C_OK;
}

int lremCommand ( client *c )
{
    robj *subject, *obj;
    obj = c->argv[3];
    long toremove;
    long removed = 0;

    if ( ( getLongFromObject (c->argv[2], &toremove) != C_OK ) )
        return C_ERR;

    subject = lookupKeyWrite (c->db, c->argv[1]);
    if ( subject == NULL || checkType (c, subject, OBJ_LIST) ) return C_ERR;

    listTypeIterator *li;
    if ( toremove < 0 )
    {
        toremove = - toremove;
        li = listTypeInitIterator (subject, - 1, LIST_HEAD);
    }
    else
    {
        li = listTypeInitIterator (subject, 0, LIST_TAIL);
    }

    listTypeEntry entry;
    while ( listTypeNext (li, &entry) )
    {
        if ( listTypeEqual (&entry, obj) )
        {
            listTypeDelete (li, &entry);
            removed ++;
            if ( toremove && removed == toremove ) break;
        }
    }
    listTypeReleaseIterator (li);

    if ( listTypeLength (subject) == 0 )
    {
        dbDelete (c->db, c->argv[1]);
    }

    addReplyLongLong (c, removed);
    return C_OK;
}

/* This is the semantic of this command:
 *  RPOPLPUSH srclist dstlist:
 *    IF LLEN(srclist) > 0
 *      element = RPOP srclist
 *      LPUSH dstlist element
 *      RETURN element
 *    ELSE
 *      RETURN nil
 *    END
 *  END
 *
 * The idea is to be able to get an element from a list in a reliable way
 * since the element is not just returned but pushed against another list
 * as well. This command was originally proposed by Ezra Zygmuntowicz.
 */

void rpoplpushHandlePush ( client *c, robj *dstkey, robj *dstobj, robj *value )
{
    /* Create the list if the key does not exist */
    if ( ! dstobj )
    {
        dstobj = createQuicklistObject ();
        quicklistSetOptions (dstobj->ptr, server.list_max_ziplist_size,
                             server.list_compress_depth);
        dbAdd (c->db, dstkey, dstobj);
    }
    listTypePush (dstobj, value, LIST_HEAD);
    /* Always send the pushed value to the client. */
    addReply (c, value);
}

int rpoplpushCommand ( client *c )
{
    robj *sobj, *value;
    if ( ( sobj = lookupKeyWrite (c->db, c->argv[1]) ) == NULL ||
         checkType (c, sobj, OBJ_LIST) ) return C_ERR;

    if ( listTypeLength (sobj) == 0 )
    {
        /* This may only happen after loading very old RDB files. Recent
         * versions of Redis delete keys of empty lists. */
        return C_ERR;
    }
    else
    {
        robj *dobj = lookupKeyWrite (c->db, c->argv[2]);
        robj *touchedkey = c->argv[1];

        if ( dobj && checkType (c, dobj, OBJ_LIST) ) return C_ERR;
        value = listTypePop (sobj, LIST_TAIL);
        /* We saved touched key, and protect it, since rpoplpushHandlePush
         * may change the client command argument vector (it does not
         * currently). */
        incrRefCount (touchedkey);
        rpoplpushHandlePush (c, c->argv[2], dobj, value);

        /* listTypePop returns an object with its refcount incremented */
        decrRefCount (value);

        /* Delete the source list when it is empty */
        if ( listTypeLength (sobj) == 0 )
        {
            dbDelete (c->db, touchedkey);
        }
        decrRefCount (touchedkey);
    }
    return C_OK;
}
